{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Coins for Fruits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #dynamic-programming #monotonic-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #动态规划 #单调队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #购买水果需要的最少金币数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>1</strong>&nbsp;开始的数组&nbsp;<code>prices</code>&nbsp;，其中&nbsp;<code>prices[i]</code>&nbsp;表示你购买第 <code>i</code>&nbsp;个水果需要花费的金币数目。</p>\n",
    "\n",
    "<p>水果超市有如下促销活动：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你花费 <code>price[i]</code>&nbsp;购买了水果&nbsp;<code>i</code>&nbsp;，那么接下来的 <code>i</code>&nbsp;个水果你都可以免费获得。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;，即使你&nbsp;<strong>可以</strong>&nbsp;免费获得水果&nbsp;<code>j</code>&nbsp;，你仍然可以花费&nbsp;<code>prices[j]</code>&nbsp;个金币去购买它以便能免费获得接下来的 <code>j</code>&nbsp;个水果。</p>\n",
    "\n",
    "<p>请你返回获得所有水果所需要的 <strong>最少</strong>&nbsp;金币数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prices = [3,1,2]\n",
    "<b>输出：</b>4\n",
    "<b>解释</b><strong>：</strong>你可以按如下方法获得所有水果：\n",
    "- 花 3 个金币购买水果 1 ，然后免费获得水果 2 。\n",
    "- 花 1 个金币购买水果 2 ，然后免费获得水果 3 。\n",
    "- 免费获得水果 3 。\n",
    "注意，虽然你可以免费获得水果 2 ，但你还是花 1 个金币去购买它，因为这样的总花费最少。\n",
    "购买所有水果需要最少花费 4 个金币。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prices = [1,10,1,1]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>你可以按如下方法获得所有水果：\n",
    "- 花 1 个金币购买水果 1 ，然后免费获得水果 2 。\n",
    "- 免费获得水果 2 。\n",
    "- 花 1 个金币购买水果 3 ，然后免费获得水果 4 。\n",
    "- 免费获得水果 4 。\n",
    "购买所有水果需要最少花费 2 个金币。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= prices[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-coins-for-fruits](https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-coins-for-fruits](https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,2]', '[1,10,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        size = len(prices)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, free: int):\n",
    "            if (i == size):\n",
    "                return 0\n",
    "            \n",
    "            if (free == 0):\n",
    "                return dfs(i + 1, i + 1) + prices[i]\n",
    "            return min(dfs(i + 1, free - 1), prices[i] + dfs(i + 1, i + 1))\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        #dp\n",
    "        n=len(prices)\n",
    "        dp=[0]*n\n",
    "        dp[0]=prices[0]\n",
    "        if n>1:\n",
    "          dp[1]=dp[0]\n",
    "          small=[(dp[0]+prices[1],1)]\n",
    "          for i in range(2,n):\n",
    "            bisect.insort(small,(dp[i-1]+prices[i],i))\n",
    "            c=i+1\n",
    "            half=(c+1)//2\n",
    "            cut=-1\n",
    "            for j in range(len(small)):\n",
    "              if small[j][1]>=half-1:\n",
    "                dp[i]=small[j][0]\n",
    "                break\n",
    "              else:\n",
    "                cut=j+1\n",
    "            if cut!=-1:\n",
    "              small=small[cut:]           \n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            n = len(prices)\n",
    "            if 2 * i >= n:\n",
    "                return prices[i-1]\n",
    "            return prices[i-1] + min(dfs(j) for j in range(i+1, 2 * i + 2))\n",
    "        return dfs(1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        for j in range(n + 1):\n",
    "            dp[n][j] = 0\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = prices[i] + dp[i + 1][i + 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i + 1][j - 1], prices[i] + dp[i + 1][i + 1])\n",
    "        # print(dp)\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        dp=np.ones((n,2))*1e6\n",
    "        dp[0][0]=prices[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=min(dp[i-1][0],dp[i-1][1])+prices[i]\n",
    "            for j in range(floor(i/2),i):\n",
    "                dp[i][1]=min(dp[j][0],dp[i][1])\n",
    "        return int(min(dp[n-1][0],dp[n-1][1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, most_right: int):\n",
    "            if i > n:\n",
    "                return 0\n",
    "            res = prices[i - 1] + dfs(i + 1, min(n, max(most_right, i + i)))\n",
    "            if i <= most_right:\n",
    "                res = min(res, dfs(i + 1, most_right))\n",
    "            return res\n",
    "        ans = dfs(1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        prices = [0] + prices\n",
    "        n = len(prices)\n",
    "\n",
    "        # 直到j都可以免费获取\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if i > j:\n",
    "                return dfs(i+1, i + i) + prices[i]\n",
    "            return min(dfs(i+1, i+i) + prices[i], dfs(i+1, j))\n",
    "            # return 0\n",
    "        ans = dfs(1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        @cache\n",
    "        def dfs(cur=0,free=0):\n",
    "            if cur == n:\n",
    "                return 0\n",
    "            ans = dfs(cur+1,cur+1) + prices[cur]\n",
    "            if free:\n",
    "                ans = min(ans,dfs(cur+1,free-1))\n",
    "            return ans\n",
    "        ans =  dfs()\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        new_p = []\n",
    "        n = len(prices)\n",
    "        for i,price in enumerate(prices):\n",
    "            new_p.append([i+1,price])\n",
    "        @cache\n",
    "        def dfs(i,num):\n",
    "            if(i>=n or i+num>=n):return 0\n",
    "            ans = inf\n",
    "            if num>0:\n",
    "                ans = dfs(i+1,num-1)\n",
    "            return min(dfs(i+1,new_p[i][0])+new_p[i][1],ans)\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, p: List[int]) -> int:\n",
    "        n=len(p)\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j>=n-1:\n",
    "                return 0\n",
    "            ans=dfs(i+1,max(j,i+i+1))+p[i]\n",
    "            if j>=i:\n",
    "                ans=min(ans,dfs(i+1,j))\n",
    "            return ans\n",
    "        return dfs(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i = 1, j = 1):  #i-水果编号- 从1开始数,所以从2开始算 #j表示没付钱的\n",
    "            if j > n:\n",
    "                return 0 \n",
    "            if i > j:  #不合法\n",
    "                print('impossible')\n",
    "                return \n",
    "            if i == j:\n",
    "                return dfs(i + 1, 2 * i + 1) + prices[i - 1]\n",
    "            if i < j:\n",
    "                return min(dfs(i+1, 2 * i + 1) + prices[i - 1], dfs(i+1, j))\n",
    "        \n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, free: int) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if free > n - i:\n",
    "                return 0\n",
    "            res = dfs(i + 1, i + 1) + prices[i]\n",
    "            if free:\n",
    "                res = min(res, dfs(i + 1, free - 1))\n",
    "            return res\n",
    "\n",
    "        dfs.cache_clear()\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        prices = [0] + prices\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=12800000)\n",
    "        def dp(ii, jj):\n",
    "            if ii == n+1:\n",
    "                return 0\n",
    "\n",
    "            nx = ii+1 + ii-1\n",
    "            nx = min(nx, n)\n",
    "            nx = max(nx, jj)\n",
    "            ans = prices[ii] + dp(ii+1, nx)\n",
    "\n",
    "            if jj >= ii:\n",
    "                ans = min(ans, dp(ii+1, jj))\n",
    "\n",
    "            # print(ii, jj, ans)\n",
    "            return ans\n",
    "\n",
    "        return dp(1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        @cache\n",
    "        def f(i,r):\n",
    "            if i==n:\n",
    "                return 0\n",
    "            ret=f(i+1,i*2+1)+prices[i]\n",
    "            if(i<=r):\n",
    "                ret=min(ret,f(i+1,r))\n",
    "            return ret\n",
    "        return f(0,-1)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, p):\n",
    "            if idx == len(prices):\n",
    "                return 0\n",
    "            res = dfs(idx + 1, idx) + prices[idx]\n",
    "            if idx <= p + p + 1:\n",
    "                res = min(res, dfs(idx + 1, p))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, -inf)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        # 每一个选择当前花钱买还是沿用上次可以免费获得的\n",
    "        n = len(prices)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, reach):\n",
    "            if i > n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            # 这次必须要买\n",
    "            if i > reach:\n",
    "                res += dfs(i + 1, i + i) + prices[i - 1]\n",
    "                # 可以选择这次买还是沿用上次\n",
    "            else:\n",
    "                res += min(dfs(i + 1, i + i) + prices[i - 1], dfs(i + 1, reach))\n",
    "            return res\n",
    "\n",
    "        return dfs(1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCoins(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, ok):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if ok > 0: # 可以免费获得的数量\n",
    "                return min(dp(i+1, ok-1), dp(i+1, i+1) + prices[i]) # 可买可不买，如果不买，后一个能免费获得的水果数量-1\n",
    "            else:\n",
    "                return dp(i+1, i+1) + prices[i]\n",
    "\n",
    "        return dp(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
